Sum root to leaf numbers

Time: O(N); Space: O(H); medium

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note:

  • A leaf is a node with no children.

Example 1:

Input: root = {TreeNode} [1,2,3]

  1
 / \
2   3

Output: 25

Explanation:

  • The root-to-leaf path 1->2 represents the number 12.

  • The root-to-leaf path 1->3 represents the number 13.

  • Therefore, sum = 12 + 13 = 25.

Example 2:

Input: = root = {TreeNode} [4,9,0,5,1]

    4
   / \
  9   0
 / \
5   1

Output: 1026

Explanation:

  • The root-to-leaf path 4->9->5 represents the number 495.

  • The root-to-leaf path 4->9->1 represents the number 491.

  • The root-to-leaf path 4->0 represents the number 40.

  • Therefore, sum = 495 + 491 + 40 = 1026.

[2]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H), H is height of BinaryTree
    """
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: integer
        """
        return self.sumNumbersRecu(root, 0)

    def sumNumbersRecu(self, root, num):
        if root is None:
            return 0

        if root.left is None and root.right is None:
            return num * 10 + root.val

        return self.sumNumbersRecu(root.left, num * 10 + root.val) + \
               self.sumNumbersRecu(root.right, num * 10 + root.val)

[4]:

s = Solution1()

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
assert s.sumNumbers(root) == 25

root = TreeNode(4)
root.left = TreeNode(9)
root.right = TreeNode(0)
root.left.left = TreeNode(5)
root.left.right = TreeNode(1)
assert s.sumNumbers(root) == 1026